package bTree.LeetCode;


//动态规划解法
public class 组合总和4 {
    public int combinationSum4(int[] nums, int target) {
        int []dp=new int[target+1];
        dp[0]=1;
        for (int i=1;i<=target;i++){
            for(int j=0;j<nums.length;j++){
                if (i>=nums[j]){
                    dp[i]+=dp[i-nums[j]];
                }
            }
        }
        return dp[target];
    }
}


//回溯,超时
public class 组合总和4 {
    int result = 0;

    public int combinationSum4(int[] nums, int target) {
        int path = 0;
        backTracking(nums, target, path);
        return result;
    }

    private void backTracking(int[] nums, int target, int path) {
        if (path >= target) {
            if (path == target) {
                result++;
            }
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            backTracking(nums, target, path + nums[i]);
        }
    }
}